◀ Prev · Parts · Full · Next ▶

Because the min cut is k, every vertex v must satisfy degree(v) ≥ k. Therefore, the sum of the degree is at least pk. But it is well known that the sum of vertex degrees equals 2|E|. The lemma follows.

The probability that the algorithm succeeds is 1 − the probability that all attempts fail. By independence, the probability that all attempts fail is ∏ ∏ i = 1 m Pr ( C i ≠ ≠ C ) = ∏ ∏ i = 1 m ( 1 − − Pr ( C i = C ) ) . {\displaystyle \prod _{i=1}^{m}\Pr(C_{i}\neq C)=\prod _{i=1}^{m}(1-\Pr(C_{i}=C)).}

By lemma 1, the probability that Ci = C is the probability that no edge of C is selected during iteration i. Consider the inner loop and let Gj denote the graph after j edge contractions, where j ∈ {0, 1, …, n − 3}. Gj has n − j vertices. We use the chain rule of conditional possibilities. The probability that the edge chosen at iteration j is not in C, given that no edge of C has been chosen before, is 1 − − k | E ( G j ) | {\displaystyle 1-{\frac {k}{|E(G_{j})|}}} . Note that Gj still has min cut of size k, so by Lemma 2, it still has at least ( n − − j ) k 2 {\displaystyle {\frac {(n-j)k}{2}}} edges.

Thus, 1 − − k | E ( G j ) | ≥ ≥ 1 − − 2 n − − j = n − − j − − 2 n − − j {\displaystyle 1-{\frac {k}{|E(G_{j})|}}\geq 1-{\frac {2}{n-j}}={\frac {n-j-2}{n-j}}} .

◀ Prev · Parts · Full · Next ▶